package com.lun.swordtowardoffer2.c14;

public class NumDistinct {

	public int numDistinct(String S, String T) {
		int len1 = S.length(), len2 = T.length();

		int[][] dp = new int[len1 + 1][len2 + 1];

		dp[0][0] = 1;

		for (int i = 0; i < len1; i++) {
			dp[i + 1][0] = 1;
			for (int j = 0; j <= i && j < len2; j++) {
				dp[i + 1][j + 1] = (S.charAt(i) == T.charAt(j) ? dp[i][j] : 0)//
						+ dp[i][j + 1];
			}
		}

		return dp[len1][len2];
	}

	public int numDistinct2(String S, String T) {
		int[] dp = new int[T.length() + 1];

		if (S.length() > 0) {
			dp[0] = 1;
		}

		for (int i = 0; i < S.length(); i++) {
			for (int j = Math.min(i, T.length() - 1); j >= 0; j--) {//从右到左
				if (S.charAt(i) == T.charAt(j)) {
					dp[j + 1] += dp[j];
				}
			}
		}

		return dp[T.length()];
	}

}
